package com.leetcode.sorts.arrays.binary_search;

import java.util.Arrays;

/**
 * @Author: WuPeng
 * @Date: 2021/5/20 11:18 上午
 *
 * 034: 在排序数组中查找元素的第一个和最后一个位置
 *      给定一个按照升序排列的整数数组 nums，和一个目标值 target。
 *      找出给定目标值在数组中的开始位置和结束位置。
 *
 *      如果数组中不存在目标值 target，返回[-1, -1]。
 *
 * 进阶：
 *      你可以设计并实现时间复杂度为O(logn)的算法解决此问题吗？
 *
 * 示例 1：
 *      输入：nums = [5,7,7,8,8,10], target = 8
 *      输出：[3,4]
 *
 * 示例2：
 *      输入：nums = [5,7,7,8,8,10], target = 6
 *      输出：[-1,-1]
 *
 * 示例 3：
 *      输入：nums = [], target = 0
 *      输出：[-1,-1]
 *
 * 目标：
 *      找到第一个大于等于目标数字 target 的下标 leftIdx，
 *      第一个大于目标数字target的下标 rightIdx
 *      判断：
 *          符合条件 leftIdx < rightIdx && rightIdx < nums.length && nums[leftIdx] == nums[rightIdx-1] == target
 *          则，返回结果 [leftIdx, rightIdx-1];
 *          否则，没有符合条件的元素 [-1, -1]。
 *
 */
public class SearchFirstAndLast_034 {

    public static int[] solution(int[] nums, int target){
        int leftIdx = binary_search(nums, target, true);
        int rightIdx = binary_search(nums, target, false) - 1;

        if (leftIdx <= rightIdx
                && rightIdx < nums.length
                && nums[leftIdx] == target
                && nums[rightIdx] == target){
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public static int binary_search(int[] nums, int target, boolean lower){
        int left=0, right=nums.length-1, ans = nums.length;
        while(left <= right){
            int mid = (left + right) >> 1;
            if (nums[mid] > target || (lower && nums[mid] >= target)){
                right = mid-1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        int[] res = solution(nums, 8);
        System.out.println(Arrays.toString(res));
    }

}
